我们对的奇偶进行分类讨论:
若是偶数,我们选择后手。对于对手每次操作,我们操作其对称的位置,将其转变为与对手操作相同的粒子。容易证得这样的操作一定合法。
若是奇数,我们可以尝试先操作最中间的位置,然后使用和上面类似的对称策略。但是由于如果全部中子最后变成了同种粒子,那么后手获胜。这条规则,这个策略并不成立。
换一个思路,我们选择后手。我们的操作策略要保证,每次我方操作后,局面状态满足一个循环不变式:
存在一个使得,前个粒子和后个粒子相反对称,且中间剩余的一段除某一个端点没被操作外,其他部分都被操作成了相同的粒子。其中,相反对称的定义是:对于任意,左起第个粒子和右起第个粒子要么都没被操作过,要么电性相反。
例如,以下情况都是满足条件的:
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
|---|
| 0 | -1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|
(三个例子中分别可以取)
注意初始状态也是满足这个条件的,取即可。
我们可以采取以下策略维护这个循环不变式:
选择后手,对于对手每次操作,我们都操作其对称的位置,将其转变为与对手操作相反的粒子。但是有两种例外情况,可能导致我们的操作不合法:
-
对手操作了中间一段剩下的那个端点。(例如在上面的第二行例子中,对手将第六格变成)。由于我们保证左右两侧是相反对称的,那么与中间一段相邻的两个粒子中,必然有一个是可操作的。我们把这个格子操作成和中间一段相同的粒子(接上面的例子,把第七格变成),易发现这样操作后循环不变式仍然满足,且的值减少了。特殊地,如果已经是,对手这样操作后必然导致所有粒子相同,根据规则后手胜。
-
对手操作了中间一段剩下的那个端点相邻的一个点,且与中段的电性相同(例如在上面的第二行例子中,对手将第七格变成)。此时我们只需要把那个端点操作成相同的粒子即可(接上面的例子,把第六格变成)。循环不变式仍然成立,且的值减少了。
如果我们一直维护了这个循环不变式,对于对手的每一个合法操作我们都有一个对应的合法操作,显然后手必胜。